In general, routing can be defined as the act of moving information from a source node to a destination node via one or more intermediate nodes in a communication network.
In a multi-hop network, nodes out of reach from each other may benefit from intermediately located nodes that can forward their messages from the source towards the destination.
Routing generally involves two basic tasks: determining suitable routing paths and transporting information through the network. In the context of the routing process, the first of these tasks is normally referred to as route determination and the latter of these tasks is often referred to as packet forwarding.
For route determination, a common approach is to span a so-called routing tree. The routing tree is normally calculated based on a well-known shortest path algorithm, implying that the determined shortest paths from the various nodes in the tree to the destination node are so-called “least cost paths” where cost is defined in an appropriate manner. In practice, the tree is often continuously built and updated to manage mobility and changing link conditions.
When a particular node in the tree wants to send a packet in the subsequent packet forwarding process, the node is considered a source node, and the packet follows the determined routing path from the source to the destination. Different nodes may send packets to the same destination over time, hence different nodes will act as source nodes and send along their respective shortest path. In addition, as multiple destinations may exist, multiple trees may be generated, each rooted at a corresponding destination.
Routing protocols generally use so-called routing metrics as a base for evaluating which path or route that will be the best for a given packet and thereby determining the optimal route to the destination. In the prior art, many different metrics have been used by the routing algorithms to determine the best, or at least a suitable route.
Often the problem is formulated in terms of finding the route that maximizes or minimizes a certain metric, where the metric may, for example, be the route bit rate capacity, the route power consumption, or the route latency. If the metric is simple enough, there are well-known efficient polynomial-time algorithms for finding the optimal route, e.g. the Bellman-Ford algorithm and the Dijkstra algorithm [8].
In the general case, however, the problem is Non-deterministic Polynomial-time hard, NP-hard [1], i.e. the computational complexity grows exponentially with the number of nodes.
The problem of finding routes under consideration of multiple performance measures, also referred to as metrics, where more than one performance measure or metric, e.g. bit rate and latency, are combined into a so-called composite metric, has been studied in the research literature, e.g. see [1, 4, 5, 6].
Unfortunately, the desire to take multiple routing metrics into account in a composite metric either makes the task of finding optimal routes computationally unfeasible using known algorithms, or when the task is simplified or relaxed, the composite metric will in general not accurately reflect the underlying optimization problem.
It is evident that the routing metric has a substantial effect on route determination, and therefore it is of utmost importance to provide improved strategies for route determination and/or enhanced metrics for determining suitable routes. Improved route determination then naturally leads to improved routing with improved performance such as higher throughput and/or reduced delay in the networks.